package graph.topologicalsort;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @Classname : CourseScheduleII
 * @Description :
 * <a href="https://leetcode.cn/problems/course-schedule-ii/">210. 课程表 II</a>
 * @Author : chentianyu
 * @Date 2023/2/2 00:08
 */


public class CourseScheduleII {

    /**
     * 方法一：深度优先搜索
     */
    private int[] ans; // 数组模拟栈
    private int index;  // 栈顶
    private int[] visited;  // visited[i] = 0-未搜索/1-搜索中/2-已搜索
    private List<List<Integer>> nexts;  // 有向图的邻接矩阵
    private boolean valid;  // 是否无环 true-无环/false-有环

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        ans = new int[numCourses];
        index = numCourses - 1;
        visited = new int[numCourses];
        nexts = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) nexts.add(new ArrayList<>());
        for (int[] prerequisite : prerequisites) nexts.get(prerequisite[1]).add(prerequisite[0]);
        valid = true;

        for (int i = 0; i < numCourses && valid; i++) {
            // 在无环的前提下，查找未搜索的节点开启搜索
            if (visited[i] == 0) dfs(i);
        }
        return valid ? ans : new int[]{};
    }

    private void dfs(int p) {
        visited[p] = 1;  // 标记为搜索中
        for (int next : nexts.get(p)) {
            if (visited[next] == 0) {  // 未搜索
                dfs(next);
                if (!valid) return;
            } else if (visited[next] == 1) {  // 搜索中
                valid = false;
                return;
            }
            // 若已搜索，由于已经入栈，一定满足顺序，无需处理
        }
        visited[p] = 2;  // 标记为已搜索
        ans[index--] = p;  // 已搜索后压栈
    }


    /************************************************************************************/


    /**
     * 方法二：广度优先搜索
     */
    public int[] findOrder2(int numCourses, int[][] prerequisites) {
        List<List<Integer>> nexts = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) nexts.add(new ArrayList());
        int[] preNums = new int[numCourses];

        // 获取每门课程的可选后续课程
        // 获取每门课程的前置课程数量
        for (int[] prerequisite : prerequisites) {
            nexts.get(prerequisite[1]).add(prerequisite[0]);
            preNums[prerequisite[0]]++;
        }
        // 将没有前置课程的课程放入队列
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (preNums[i] == 0) q.offer(i);
        }
        // 广度优先遍历课程
        int[] ans = new int[numCourses];
        int index = 0;
        while (!q.isEmpty()) {
            int cur = q.poll();
            ans[index++] = cur;  // 出队列时记录顺序
            for (int next : nexts.get(cur)) {
                preNums[next]--;
                // 当前课程的前置课程都已完成才可进行学习
                // 有环则永远不可能放入队列！
                if (preNums[next] == 0) q.offer(next);
            }
        }
        if (index < numCourses) return new int[]{};
        return ans;
    }
}
